package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/correct-a-binary-tree/'>纠正二叉树(Correct a Binary Tree)</a>
 * <p>你有一棵二叉树，这棵二叉树有个小问题，其中有且只有一个无效节点，它的右子节点错误地指向了与其在同一层且在其右侧的一个其他节点。</p>
 * <p>给定一棵这样的问题二叉树的根节点 root ，将该无效节点及其所有子节点移除（除被错误指向的节点外），然后返回新二叉树的根结点。</p>
 * <p>
 * 测试用例的输入由三行组成：
 * <ul>
 *     <li>TreeNode root</li>
 *     <li>int fromNode （在 correctBinaryTree 中不可见）</li>
 *     <li>int toNode （在 correctBinaryTree 中不可见）</li>
 * </ul>
 * 当以 root 为根的二叉树被解析后，值为 fromNode 的节点 TreeNode 将其右子节点指向值为 toNode 的节点 TreeNode 。然后， root 传入 correctBinaryTree 的参数中。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: root = [1,2,3], fromNode = 2, toNode = 3
 *                      1
 *                     / \
 *                    2   3
 *      输出: [1,null,3]
 *      解释: 值为 2 的节点是无效的，所以移除之。
 *
 * 示例 2:
 *      输入: root = [8,3,1,7,null,9,4,2,null,null,null,5,6], fromNode = 7, toNode = 4
 *                      8
 *                    /  \
 *                   3    1
 *                  /    / \
 *                 7    9   4
 *                /        / \
 *               2        5   6
 *      输出: [8,3,1,null,null,9,4,null,null,5,6]
 *      解释: 值为 7 的节点是无效的，所以移除这个节点及其子节点 2。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>树中节点个数的范围是 [3, 10^4] 。</li>
 *     <li>-10^9 <= Node.val <= 10^9</li>
 *     <li>所有节点的值 Node.val 互不相同</li>
 *     <li>fromNode != toNode</li>
 *     <li>fromNode 和 toNode 将出现在树中的同一层。</li>
 *     <li>toNode 在 fromNode 的右侧。</li>
 *     <li>fromNode.right 在测试用例的树中建立后为 null 。</li>
 * </ul>
 * </p>
 * <p>
 *
 * @author c2b
 * @since 2023/12/5 13:36
 */
public class LC1660CorrectBinaryTree_M {

    public TreeNode correctBinaryTree(TreeNode root) {
        return dfs(root, new HashSet<>());
    }

    private TreeNode dfs(TreeNode currNode, Set<TreeNode> visited) {
        if (currNode == null || visited.contains(currNode.right)) {
            return null;
        }
        visited.add(currNode);
        currNode.right = dfs(currNode.right, visited);
        currNode.left = dfs(currNode.left, visited);
        return currNode;
    }
}
